package com.lw.leetcode.bit.c;

import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 1542. 找出最长的超赞子字符串
 *
 * @author liw
 * @version 1.0
 * @date 2022/8/24 15:58
 */
public class LongestAwesome {

    public static void main(String[] args) {
        LongestAwesome test = new LongestAwesome();

        // 5
        String str = "3242415";

        // 1
//        String str = "12345678";

        // 6
//        String str = "213123";

        // 2
//        String str = "00";

        // 3
//        String str = "51224";

        // 5
//        String str = "185801630663498";

        int i = test.longestAwesome(str);
        System.out.println(i);

    }

    public int longestAwesome(String s) {
        int length = s.length();
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int item = 0;
        int max = 0;
        for (int i = 0; i < length; i++) {
            int c = s.charAt(i) - '0';
            item ^= (1 << c);
            Integer v = map.get(item);
            if (v == null) {
                map.put(item, i);
            } else {
                max = Math.max(max, i - v);
            }
            for (int j = 0; j < 10; j++) {
                int t = 1 << j;
                if (item != (item | t)) {
                    v = map.get(item + t);
                } else {
                    v = map.get(item - t);
                }
                if (v != null) {
                    max = Math.max(max, i - v);
                }
            }
        }
        return max;
    }

}
